\documentclass[E:/GsjzTle/main/main.tex]{subfiles}
\begin{document}

有向图，$s$到$t$的第$k$短路。

\begin{lstlisting}
int n , m , s , t , k ;
vector<pii> g1[N] , g2[N] ; 
struct Dij
{
	int dis[N] ;
	priority_queue<pii , vector<pii> , greater<pii> > q ;
	void init()
	{
		memset(dis , inf , sizeof(dis)) ;	
	}
	void dijkstra(int s)
	{
		dis[s] = 0 ;
		q.push(make_pair(0 , s)) ;
		while(!q.empty())
		{
			pii p = q.top() ;
			q.pop() ;
			int u = p.second ;
			if(p.first != dis[u])  continue ; //优化，不用旧值更新。
			for(vector<pii>::iterator x = g2[u].begin() ; x != g2[u].end() ; x ++)
			//for(auto x : g2[u])
			{
				int v = (*x).fi , w = (*x).se ;
				if(dis[v] > dis[u] + w)
				{
					dis[v] = dis[u] + w ;
					q.push(make_pair(dis[v] , v)) ;
				}
			}
		}
	}
} dij ;
struct node
{
	int u , g , h ;
	bool operator < (const node &s) const
	{
		return g + h > s.g + s.h ;
	}
} ;
priority_queue<node> q ;
int num[N] ;
int astar()
{
	mem0(num) ;
	while(!q.empty())  q.pop() ;
	q.push(node{s , 0 , dij.dis[s]}) ;
	while(!q.empty())
	{
		int u = q.top().u , g = q.top().g ;
		q.pop() ;
		num[u] ++ ;
		if(num[u] == k && u == t)  return g ;
		if(num[u] > k)  continue ;
		for(vector<pii>::iterator x = g1[u].begin() ; x != g1[u].end() ; x ++)
		//for(auto x : g1[u])
		{
			int v = (*x).fi , w = (*x).se ; 
			q.push(node{v , g + w , dij.dis[v]}) ;
		}
	}
	return -1 ;
}
int main()
{
	rr(n , m) ;
	rep(i , 1 , m)
	{
		int u , v , w ;
		rr(u , v) , r(w) ;
		g1[u].pb({v , w}) ;
		g2[v].pb({u , w}) ;
	}
	rr(s , t) , r(k) ;
	if(s == t)  k ++ ;
	dij.init() ;
	dij.dijkstra(t) ;
	we(astar()) ;
	return 0 ; 
}

\end{lstlisting}

\end{document}


